/** ANSI C ANTLR v3 grammar

Translated from Jutta Degener's 1995 ANSI C yacc grammar by Terence Parr
July 2006.  The lexical rules were taken from the Java grammar.

Jutta says: "In 1985, Jeff Lee published his Yacc grammar (which
is accompanied by a matching Lex specification) for the April 30, 1985 draft
version of the ANSI C standard.  Tom Stockfisch reposted it to net.sources in
1987; that original, as mentioned in the answer to question 17.25 of the
comp.lang.c FAQ, can be ftp'ed from ftp.uu.net,
   file usenet/net.sources/ansi.c.grammar.Z.
I intend to keep this version as close to the current C Standard grammar as
possible; please let me know if you discover discrepancies. Jutta Degener, 1995"

Generally speaking, you need symbol table info to parse C; typedefs
define types and then IDENTIFIERS are either types or plain IDs.  I'm doing
the min necessary here tracking only type names.  This is a good example
of the global scope (called Symbols).  Every rule that declares its usage
of Symbols pushes a new copy on the stack effectively creating a new
symbol scope.  Also note rule declaration declares a rule scope that
lets any invoked rule see isTypedef boolean.  It's much easier than
passing that info down as parameters.  Very clean.  Rule
direct_declarator can then easily determine whether the IDENTIFIER
should be declared as a type name.

I have only tested this on a single file, though it is 3500 lines.

This grammar requires ANTLR v3.0.1 or higher.

Terence Parr
July 2006
*/
grammar C;
options {
	output=AST;
	ASTLabelType=CommonTree;
	backtrack=true;
	memoize=true;
	k=2;
}

tokens {
	CAST;
	IF; SWITCH;
	FOR; WHILE; DO;
	CONTINUE; BREAK; GOTO; RETURN;
	LABEL; CASE; DEFAULT;
	CALL;
	INDEX;
	DEREFERENCE;
	SIZEOF;
	MEMBER_ACCESS; // x.y
	INDIRECT_MEMBER_ACCESS; // x->y
	PREFIX_INC; // ++i
	POSTFIX_INC; // i++
	PREFIX_DEC; // --i
	POSTFIX_DEC; // i--
	CONDITIONAL; // b ? a : c
	BLOCK; // { }
	COMMA; // a, b

	ARRAY; POINTER; BASIC_TYPE;
	FUNCTION; VARIABLE; PARAMETER_LIST;
	VARARGS; // (, ...)
	INITIALIZER_LIST;
	UNDEFINED;

	EXTERN='extern';
	STATIC='static';
	AUTO='auto';
	REGISTER='register';

	VOID='void';
	CHAR='char';
	SHORT='short';
	INT='int';
	LONG='long';
	FLOAT='float';
	DOUBLE='double';
	SIGNED='signed';
	UNSIGNED='unsigned';

	CONST='const';
	VOLATILE='volatile';
}

translation_unit
	: external_declaration+
	;

external_declaration
options { k=1; }
scope
{
	CommonTree basic_type;
}
@init
{
	CommonTree r = (CommonTree)adaptor.nil();
	$external_declaration::basic_type 
		= (CommonTree)adaptor.becomeRoot(new TypeTree(UNDEFINED), r);
}
	: ( declaration_specifiers? function_declarator '{' )=> function_definition
	| declaration
	;

function_definition
	:	(declaration_specifiers
		{ $external_declaration::basic_type 
			= $declaration_specifiers.tree; }
		)?
		function_declarator compound_statement
		-> ^(FUNCTION function_declarator compound_statement)
	;

function_declarator
@after
{
	((TypeTree)$external_declaration::basic_type).setType();
}
	: 	(pointer[$external_declaration::basic_type]
		{ $external_declaration::basic_type = $pointer.pointer_type; }
		)? 
		function_direct_declarator
		-> {$external_declaration::basic_type} function_direct_declarator
	;

function_direct_declarator
	:   IDENTIFIER function_declarator_suffix
	;

function_declarator_suffix
	:   '(' parameter_type_list ')'
		-> ^(PARAMETER_LIST parameter_type_list)
    |   '(' ')'
    	-> PARAMETER_LIST
	;

parameter_type_list
	: 	parameter_list 
		(',' '...' -> parameter_list VARARGS
		|          -> parameter_list
		)
	;

parameter_list
	: 	parameter_declaration (',' parameter_declaration)*
		-> parameter_declaration+
	;

parameter_declaration
	: 	declaration_specifiers 
		declarator[$declaration_specifiers.tree]+
		-> ^(VARIABLE declarator)+
	;

declaration
	: 	declaration_specifiers
		{ $external_declaration::basic_type = $declaration_specifiers.tree; }
		init_declarator_list? ';'
		-> init_declarator_list
	;

init_declarator_list
	: 	init_declarator (',' init_declarator)*
		-> init_declarator+
	;

init_declarator
	: 	declarator[$external_declaration::basic_type] 
		('=' initializer)?
		-> ^(VARIABLE declarator initializer?)
	;

declarator[CommonTree t]
scope
{
	CommonTree type;
}
@init
{
	$declarator::type = (CommonTree)adaptor.dupTree($t);
}
@after
{
	((TypeTree)$declarator::type).setType();
}
	: 	(pointer[$declarator::type]
		{ $declarator::type = $pointer.pointer_type; }
		)? 
		direct_declarator
		-> {$declarator::type} direct_declarator
	;

direct_declarator
scope
{
	CommonTree basic_type;
}
@init
{
	$direct_declarator::basic_type = $declarator::type;
}
	: 	IDENTIFIER 
		(declarator_suffix
		{ $declarator::type = $declarator_suffix.tree; }
		)?
		-> IDENTIFIER
	;

declarator_suffix
	: 	'[' constant_expression ']' s=declarator_suffix
		-> ^(ARRAY<TypeTree> $s constant_expression)
	| 	'[' constant_expression ']'
		-> ^(ARRAY<TypeTree> {$direct_declarator::basic_type} constant_expression)
    | 	'[' ']'
    	-> ^(ARRAY<TypeTree> {$direct_declarator::basic_type} UNDEFINED)
	;

initializer
	: assignment_expression -> assignment_expression
	| '{' initializer_list ','? '}' -> ^(INITIALIZER_LIST initializer_list)
	;

initializer_list
	: initializer (',' initializer)* -> initializer+
	;

declaration_specifiers
	:	(	s+=storage_class_specifier
		|	s+=type_specifier
		|	s+=type_qualifier
		)+ -> ^(BASIC_TYPE<TypeTree> $s+)
	;

storage_class_specifier
	: EXTERN -> EXTERN<TypeTree>
	| STATIC -> STATIC<TypeTree>
	| AUTO -> AUTO<TypeTree>
	| REGISTER -> REGISTER<TypeTree>
	;

type_specifier
	: VOID -> VOID<TypeTree>
	| CHAR -> CHAR<TypeTree>
	| SHORT -> SHORT<TypeTree>
	| INT -> INT<TypeTree>
	| LONG -> LONG<TypeTree>
	| FLOAT -> FLOAT<TypeTree>
	| DOUBLE -> DOUBLE<TypeTree>
	| SIGNED -> SIGNED<TypeTree>
	| UNSIGNED -> UNSIGNED<TypeTree>
	;

type_qualifier
	: CONST -> CONST<TypeTree>
	| VOLATILE -> VOLATILE<TypeTree>
	;

specifier_qualifier_list
	: ( s+=type_qualifier | s+=type_specifier )+ -> ^(BASIC_TYPE $s+)
	;

pointer[CommonTree target_type] returns [CommonTree pointer_type]
scope
{
	CommonTree t;
}
	: 	'*' q+=type_qualifier+ 
		{
			$pointer::t = (CommonTree)adaptor.nil();
			$pointer::t = (CommonTree)adaptor.becomeRoot(
				new TypeTree(POINTER),
				$pointer::t
			);
			adaptor.addChild($pointer::t, $target_type);
			for (Object o : $q)
			{
				adaptor.addChild($pointer::t, o);
			}
			$pointer_type = $pointer::t;
		}
		(
		ptr=pointer[$pointer::t]
		{ $pointer_type = $ptr.pointer_type; }
		)?
		->
	|	'*' 
		{
			$pointer::t = (CommonTree)adaptor.nil();
			$pointer::t = (CommonTree)adaptor.becomeRoot(
				new TypeTree(POINTER),
				$pointer::t
			);
			adaptor.addChild($pointer::t, $target_type);
		}
		ptr=pointer[$pointer::t]
		{ $pointer_type = $ptr.pointer_type; }
		->
	| 	'*'
		{
			$pointer::t = (CommonTree)adaptor.nil();
			$pointer::t = (CommonTree)adaptor.becomeRoot(
				new TypeTree(POINTER),
				$pointer::t
			);
			adaptor.addChild($pointer::t, $target_type);
			$pointer_type = $pointer::t;
		}
		->
	;

type_name
scope {
	CommonTree type;
}
	:	specifier_qualifier_list
		{ $type_name::type = $specifier_qualifier_list.tree; }
		(pointer[$type_name::type]
		{ $type_name::type = $pointer.pointer_type; }
		)?
		-> { $type_name::type }
	;

// E x p r e s s i o n s

argument_expression_list
	:   assignment_expression (','! assignment_expression)*
	;

additive_expression
	: (multiplicative_expression) 
		( '+'<ExpressionTree>^ multiplicative_expression 
		| '-'<ExpressionTree>^ multiplicative_expression
		)*
	;

multiplicative_expression
	: (cast_expression) 
		( '*'<ExpressionTree>^ cast_expression 
		| '/'<ExpressionTree>^ cast_expression 
		| '%'<ExpressionTree>^ cast_expression
		)*
	;

cast_expression
	:	'(' type_name ')' cast_expression
		-> ^(CAST<ExpressionTree> type_name cast_expression)
	|	unary_expression
	;

unary_expression
	: postfix_expression
	| '++' unary_expression -> ^(PREFIX_INC<ExpressionTree> unary_expression)
	| '--' unary_expression -> ^(PREFIX_DEC<ExpressionTree> unary_expression)
	| unary_operator cast_expression -> ^(unary_operator cast_expression)
	| 'sizeof' unary_expression -> ^(SIZEOF<ExpressionTree> unary_expression)
	| 'sizeof' '(' type_name ')' -> ^(SIZEOF<ExpressionTree> type_name)
	;

postfix_expression
	:   (primary_expression -> primary_expression)
        (   '[' e=expression ']'
        	-> ^(INDEX<ExpressionTree> $postfix_expression $e)
        |   '(' ')'
        	-> ^(CALL<ExpressionTree> $postfix_expression)
        |   '(' args=argument_expression_list ')'
        	-> ^(CALL<ExpressionTree> $postfix_expression $args)
        |   '.' id=IDENTIFIER
        	-> ^(MEMBER_ACCESS<ExpressionTree> $postfix_expression $id)
        |   '->' id=IDENTIFIER
        	-> ^(INDIRECT_MEMBER_ACCESS<ExpressionTree> $postfix_expression $id)
        |   '++' -> ^(POSTFIX_INC<ExpressionTree> $postfix_expression)
        |   '--' -> ^(POSTFIX_DEC<ExpressionTree> $postfix_expression)
        )*
	;

unary_operator
	: '&'<ExpressionTree>
	| '*'<ExpressionTree>
	| '+'<ExpressionTree>
	| '-'<ExpressionTree>
	| '~'<ExpressionTree>
	| '!'<ExpressionTree>
	;

primary_expression
	: IDENTIFIER<ExpressionTree>
	| constant
	| '('! expression ')'!
	;

constant
    :   HEX_LITERAL<ExpressionTree>
    |   OCTAL_LITERAL<ExpressionTree>
    |   DECIMAL_LITERAL<ExpressionTree>
    |	CHARACTER_LITERAL<ExpressionTree>
	|	STRING_LITERAL<ExpressionTree>
    |   FLOATING_POINT_LITERAL<ExpressionTree>
    ;

/////

expression
	: 	(assignment_expression -> assignment_expression)
		(
		',' e=assignment_expression
		-> ^(COMMA<ExpressionTree> $expression $e)
		)*
	;

constant_expression
	: conditional_expression
	;

assignment_expression
	: lvalue assignment_operator^ assignment_expression
	| conditional_expression
	;
	
lvalue
	:	unary_expression
	;

assignment_operator
	: '='<ExpressionTree>
	| '*='<ExpressionTree>
	| '/='<ExpressionTree>
	| '%='<ExpressionTree>
	| '+='<ExpressionTree>
	| '-='<ExpressionTree>
	| '<<='<ExpressionTree>
	| '>>='<ExpressionTree>
	| '&='<ExpressionTree>
	| '^='<ExpressionTree>
	| '|='<ExpressionTree>
	;

conditional_expression
	: 	logical_or_expression
	|	logical_or_expression
		'?' e1=expression ':' e2=conditional_expression
		-> ^(CONDITIONAL<ExpressionTree> logical_or_expression $e1 $e2)
	;

logical_or_expression
	: logical_and_expression ('||'<ExpressionTree>^ logical_and_expression)*
	;

logical_and_expression
	: inclusive_or_expression ('&&'<ExpressionTree>^ inclusive_or_expression)*
	;

inclusive_or_expression
	: exclusive_or_expression ('|'<ExpressionTree>^ exclusive_or_expression)*
	;

exclusive_or_expression
	: and_expression ('^'<ExpressionTree>^ and_expression)*
	;

and_expression
	: equality_expression ('&'<ExpressionTree>^ equality_expression)*
	;
equality_expression
	: relational_expression 
		(('=='<ExpressionTree>|'!='<ExpressionTree>)^ relational_expression)*
	;

relational_expression
	: shift_expression 
		(('<'<ExpressionTree>
		 |'>'<ExpressionTree>
		 |'<='<ExpressionTree>
		 |'>='<ExpressionTree>
		 )^ shift_expression)*
	;

shift_expression
	: additive_expression 
		(('<<'<ExpressionTree>
		 |'>>'<ExpressionTree>
		 )^ additive_expression)*
	;

// S t a t e m e n t s

statement
	: labeled_statement
	| compound_statement
	| expression_statement
	| selection_statement
	| iteration_statement
	| jump_statement
	;

labeled_statement
	: IDENTIFIER ':' statement
		-> ^(LABEL IDENTIFIER statement)
	| 'case' constant_expression ':' statement
		-> ^(CASE constant_expression statement)
	| 'default' ':' statement
		-> ^(DEFAULT statement)
	;

compound_statement
	: '{' declaration* statement_list? '}'
		-> ^(BLOCK declaration* statement_list?)
	;

statement_list
	: statement+
	;

expression_statement
	: ';' -> BLOCK
	| expression ';'!
	;

selection_statement
	: 'if' '(' expression ')' s1=statement (options {k=1; backtrack=false;}:'else' s2=statement)?
		-> ^(IF expression $s1 $s2?)
	| 'switch' '(' expression ')' statement
		-> ^(SWITCH expression statement)
	;

iteration_statement
	: 'while' '(' expression ')' statement
		-> ^(WHILE expression statement)
	| 'do' statement 'while' '(' expression ')' ';'
		-> ^(DO expression statement)
	| 'for' '(' e1=expression_statement e2=expression_statement e3=expression? ')' statement
		-> ^(FOR $e1 $e2 $e3? statement)
	;

jump_statement
	: 'goto' IDENTIFIER ';' -> ^(GOTO IDENTIFIER)
	| 'continue' ';' -> CONTINUE
	| 'break' ';' -> BREAK
	| 'return' ';' -> RETURN
	| 'return' expression ';' -> ^(RETURN expression)
	;

IDENTIFIER
	:	LETTER (LETTER|'0'..'9')*
	;
	
fragment
LETTER
	:	'$'
	|	'A'..'Z'
	|	'a'..'z'
	|	'_'
	;

CHARACTER_LITERAL
    :   '\'' ( EscapeSequence | ~('\''|'\\') ) '\''
    ;

STRING_LITERAL
    :  '"' ( EscapeSequence | ~('\\'|'"') )* '"'
    ;

HEX_LITERAL : '0' ('x'|'X') HexDigit+ IntegerTypeSuffix? ;

DECIMAL_LITERAL : ('0' | '1'..'9' '0'..'9'*) IntegerTypeSuffix? ;

OCTAL_LITERAL : '0' ('0'..'7')+ IntegerTypeSuffix? ;

fragment
HexDigit : ('0'..'9'|'a'..'f'|'A'..'F') ;

fragment
IntegerTypeSuffix
	:	('u'|'U')? ('l'|'L')
	|	('u'|'U')  ('l'|'L')?
	;

FLOATING_POINT_LITERAL
    :   ('0'..'9')+ '.' ('0'..'9')* Exponent? FloatTypeSuffix?
    |   '.' ('0'..'9')+ Exponent? FloatTypeSuffix?
    |   ('0'..'9')+ Exponent FloatTypeSuffix?
    |   ('0'..'9')+ Exponent? FloatTypeSuffix
	;

fragment
Exponent : ('e'|'E') ('+'|'-')? ('0'..'9')+ ;

fragment
FloatTypeSuffix : ('f'|'F'|'d'|'D') ;

fragment
EscapeSequence
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   OctalEscape
    ;

fragment
OctalEscape
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UnicodeEscape
    :   '\\' 'u' HexDigit HexDigit HexDigit HexDigit
    ;

WS  :  (' '|'\r'|'\t'|'\u000C'|'\n') {$channel=HIDDEN;}
    ;

COMMENT
    :   '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
    ;

LINE_COMMENT
    : '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    ;

// ignore #line info for now
LINE_COMMAND 
    : '#' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    ;
